﻿// 版权所有：
// 文 件  名：InsertionSort.cs
// 功能描述：
// 创建标识：Seven Song(m.sh.lin0328@163.com) 2014/3/23 14:59:59
// 修改描述：
//----------------------------------------------------------------*/
using System;
using System.Collections.Generic;

using System.Text;

namespace MSL.Utility.Sort
{
    /// <summary>
    /// 插入排序
    /// </summary>
    public class InsertSort : ISort
    {
        /// <summary>复杂度 О(n²)
        /// 插入排序 原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，
        /// 通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        public void Desc<T>(IList<T> list) where T : IComparable
        {
            for (int i = 1; i < list.Count; i++)
            {
                T temp = list[i];
                int j = i;
                while ((j > 0) && (temp.CompareTo(list[j - 1]) > 0))
                {
                    list[j] = list[j - 1];
                    j--;
                }
                list[j] = temp;
            }
        }
        /// <summary>
        /// 
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        public void Asc<T>(IList<T> list) where T : IComparable
        {
            for (int i = 1; i < list.Count; i++)
            {
                T temp = list[i];
                int j = i;
                while ((j > 0) && (temp.CompareTo(list[j - 1]) < 0))
                {
                    list[j] = list[j - 1];
                    j--;
                }
                list[j] = temp;
            }
        }
    }
}
